package com.itheima.algorithm.priorityqueue;

import com.itheima.algorithm.leetcode.ListNode;

/**
 * @author: TylerZhong
 * @description: 合并多个有序链表
 */
public class E01Leetcode23 {
    public ListNode mergeKLists(ListNode[] lists) {
        MinHeap minHeap = new MinHeap(lists.length);
        //1. 将链表的头节点加入小顶堆
        for (ListNode list : lists) {
            if (list != null) {
                minHeap.offer(list);
            }
        }
        // 2. 不断从小顶堆移除最小元素，加入新链表
        ListNode sentinel = new ListNode(-1, null);
        ListNode tail = sentinel;
        while (!minHeap.isEmpty()) {
            ListNode min = minHeap.poll();
            tail.next = min;
            tail = min;
            if (min.next != null) {
                minHeap.offer(min.next);
            }
        }
        return sentinel.next;
    }

    public static void main(String[] args) {
        ListNode[] lists = {
                ListNode.of(1, 4, 5),
                ListNode.of(1, 3, 4),
                ListNode.of(2,6),
                null
        };

        ListNode listNode = new E01Leetcode23().mergeKLists(lists);
        System.out.println(listNode);
    }
}
